// https://leetcode.cn/problems/beautiful-arrangement-ii/
// Created by ade on 2022/9/8.
// [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 思路： 1 2 3 4 5 6 7 8
    // k = 1  1 2 3 4 5 6 7 8 [1]
    // k = 2  1 3 2 4 5 6 7 8 [2,1]
    // k = 3  1 4 2 3 5 6 7 8 [3,2,1]
    // k = 4  1 5 2 4 3 6 7 8 [4,3,2,1]
    // k = 5  1 6 2 5 3 4 7 8 [5,4,3,2,1]
    // k = 6  1 7 2 6 3 5 4 8 [6,5,4,3,2,1]
    // k = 7  1 8 2 7 3 6 4 5 [7,6,5,4,3,2,1]
    vector<int> constructArray1(int n, int k) {
        vector<int> res(n);
        for (int i = 1; i <= n; i++) {
            res[i - 1] = i;
        }
        for (int j = 1; j < n; j++) {
            if (j % 2 == 1) {
                res[j] = res[j - 1] + k;
            } else {
                res[j] = res[j - 1] - k;
            }
            k--;
            if (k <= 0)break;
        }
        return res;
    }

    vector<int> constructArray(int n, int k) {
        vector<int> res(n, 0);
        iota(res.begin(), res.end(), 1);
        for (int j = 1; j < n; j++) {
            if (j % 2 == 1) {
                res[j] = res[j - 1] + k;
            } else {
                res[j] = res[j - 1] - k;
            }
            k--;
            if (k <= 0)break;
        }
        return res;
    }
};

int main() {
    Solution so;
    auto res = so.constructArray(8, 1);
    for (auto i:res) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}